1. Field of the Invention
The present invention relates generally to computer program (i.e., software) compilers and more particularly to optimizers in computer program compilers that perform an optimization known as partial redundancy elimination (PRE).
2. Related Art
The Static Single Assignment Form (SSA) is a widely-used program representation in optimizing compilers because it provides accurate use-definition (use-def) relationships among the program variables in a concise form. It is described in detail in R Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Trans. on Programming Languages and Systems, 13(4):451-490, October 1991, which is incorporated herein by reference in its entirety.
The SSA form, which is well-known in the relevant art(s), can be briefly described as a form where each definition of a variable is given a unique version, and different versions of the same variable can be regarded as different program variables. Each use of a variable version can only refer to a single reaching definition. When several definitions of a variable, a.sub.1, a.sub.2, . . . , a.sub.m, reach a common node (called a merging node) in the control flow graph of the program, a .phi. function assignment statement, a.sub.n =.phi.(a.sub.1, a.sub.2, . . . , a.sub.m), is inserted to merge the variables into the definition of a new variable version a.sub.n. Thus, the semantics of single reaching definitions are maintained.
Optimizations based on SSA all share the common characteristic that they do not require traditional iterative data flow analysis in their solutions. They take advantage of the sparse representation of SSA. In a sparse form, information associated with an object is represented only at places where it changes, or when the object actually occurs in the program. Because it does not replicate information over the entire program, a sparse representation conserves memory space. Therefore, information can be propagated through the sparse representation in a smaller number of steps, speeding up most algorithms.
Many efficient global optimization algorithms have been developed based on SSA. Among these optimizations are dead store elimination, constant propagation, value numbering, induction variable analysis, live range computation, and global code motion. However, partial redundancy elimination (PRE), a powerful optimization algorithm, was noticeably missing among SSA-based optimizations. PRE was first described in E. Morel and C. Renvoise, Global Optimization by Suppression of Partial Redundancies, Comm. ACM, 22(2): 96-103, February 1979, which is incorporated herein by reference in its entirety. PRE, which has since become an important component in many global optimizers, targets partially redundant computations in a program, and removes global common sub-expressions and moves invariant computations out of loops. In other words, by performing data flow analysis on a computation, it determines where in the program to insert the computation. These insertions in turn cause partially redundant computations to become fully redundant, and therefore safe to delete.
Given the fact that PRE was not among SSA-based optimizations, a method for performing SSA-based PRE of expressions, known as SSAPRE, along with a detailed description of SSA and PRE was disclosed and described in detail in a commonly-owned, co-pending application entitled "System, Method, and Computer Program Product for Partial Redundancy Elimination Based on Static Single Assignment Form During Compilation" having application Ser. No. 08/873,895, now U.S. Pat. No. 6,026,241, which is incorporated herein by reference in its entirety.
Furthermore, a method to extend SSAPRE to perform sparse PRE for computations in general (i.e., not just expressions) and to more specifically perform register promotion was disclosed and described in detail in a commonly-owned, co-pending application filed concurrently herewith entitled "Method, System, and Computer Program Product for Performing Register Promotion via Load and Store Placement Optimization within an Optimizing Compiler" having application Ser. No. 09/097,713 (Attorney Docket No. 15-4-658.00), which is incorporated herein by reference in its entirety.
Another optimization done by compilers is speculative code motion (also referred to as speculation). Speculation refers to the placement of computations (e. g., expressions, loads, stores, assignments, etc.) by a compiler in positions in the program that results in some paths being executed more efficiently while some paths execute less efficiently. In order to result in a net speed-up in the overall execution of the program, the improved paths must be executed more frequently than the penalized paths. Thus, speculation is best performed based on the execution profile of the program being compiled. A compiler will generally analyze the profitability of inserting speculative code by focusing on each cross-over point of execution paths and then make individual decisions. This is illustrated in FIGS. 1A and 1B.
In FIG. 1A, path 101 and path 103 of a computer program intersect at a cross-over point 105. The computation "a+b" is originally computed during path 101 after the cross-over point 105. If analysis of the software code reveals, however, that path 101 is executed more often than path 103, speculation may move the computation of "a+b" to path 103 before the cross-over point 105 as shown in FIG. 1B. The result of speculation makes path 101 execute more efficiently and path 103 execute less efficiently (i.e., path 103 is "penalized"). Yet, given the proportional execution frequencies between path 101 and path 103, the overall program of FIG. 1B executes more quickly.
Conventional code speculation, as a result, is greatly limited in the speculative code that may be generated. That is, there is no known polynomial time algorithm that may make decisions to simultaneously perform a set of speculation code placement at multiple places while taking into account the execution of all affected blocks. Furthermore no method exists for performing code speculation within PRE. Therefore, what is needed is method, system, and computer program product for extending sparse PRE to support speculative code motion within an optimizing compiler.